package com.wtgroup.demo.mianshi.算法.二叉树;

import com.wtgroup.demo.common.judge.Judger;
import com.wtgroup.demo.common.util.RandomUtil;
import com.wtgroup.demo.common.util.Tools;
import lombok.AllArgsConstructor;
import lombok.NoArgsConstructor;

import java.util.ArrayList;

/**
 * 求二叉树中最大的二叉搜索子树, 返回其头节点
 *
 * @author nisus
 * @version 0.1
 * @since 2023/5/3 9:37
 */
public class Q_最大二叉搜索子树 {
    public static void main(String[] args) {
        Judger.of(() -> {
            Node tree = generateRandomBST(RandomUtil.randomInt(0, 30), RandomUtil.randomInt());

            Info info = doit(tree);

            int refer = Tester.right(tree);

            return info.maxBstSize == refer;
        }).setIterCount(10000).start().print();
    }

    static Info doit(Node head) {
        if (head == null) {
            // 为了方便下文编码. !! max 放-∞, min 放+∞
            return new Info(true, Integer.MIN_VALUE, Integer.MAX_VALUE, 0, null);
            // return null;
        }

        if (head.left == null && head.right == null) {
            return new Info(true, head.value, head.value, 1, head);
        }

        Info leftInfo = doit(head.left);
        Info rightInfo = doit(head.right);

        boolean isBst = false;
        if (leftInfo.isBst && rightInfo.isBst) {
            isBst = leftInfo.max < head.value && head.value < rightInfo.min;
        }

        Info info = new Info();
        info.isBst = isBst;
        if (isBst) {
            info.maxBstHead = head;
            info.maxBstSize = leftInfo.maxBstSize + rightInfo.maxBstSize + 1;
            // null 节点的 max 是 -∞, 故必定留下正常值
            info.max = Tools.max(leftInfo.max, rightInfo.max, head.value);
            info.min = Tools.min(leftInfo.min, rightInfo.min, head.value);
            // info.max = max;
            // info.min = min;
        } else {
            if (leftInfo.maxBstSize > rightInfo.maxBstSize) {
                info.maxBstHead = leftInfo.maxBstHead;
                info.maxBstSize = leftInfo.maxBstSize;
                info.max = -1; // isBst false , max,min 无意义了
                info.min = -1;
            } else {
                info.maxBstHead = rightInfo.maxBstHead;
                info.maxBstSize = rightInfo.maxBstSize;
                info.max = -1;
                info.min = -1;
            }
        }

        return info;
    }

    @NoArgsConstructor
    @AllArgsConstructor
    static class Info {
        // boolean isNull;
        // 当前整个子树是不是搜索子树
        boolean isBst;
        // 左子树里的最大值要<=我, 右子树的最小值要>=我
        int max;
        int min;
        // 子树里最大搜索子树节点数
        int maxBstSize;
        Node maxBstHead;
    }

    // 为了验证
    // 对数器方法
    public static Node generateRandomBST(int maxLevel, int maxValue) {
        return generate(1, maxLevel, maxValue);
    }

    // 为了验证
    // 对数器方法
    public static Node generate(int level, int maxLevel, int maxValue) {
        if (level > maxLevel || Math.random() < 0.5) {
            return null;
        }
        Node head = new Node((int) (Math.random() * maxValue));
        head.left = generate(level + 1, maxLevel, maxValue);
        head.right = generate(level + 1, maxLevel, maxValue);
        return head;
    }


    static class Tester {
        // 为了验证
        // 对数器方法
        public static int right(Node head) {
            if (head == null) {
                return 0;
            }
            int h = getBSTSize(head);
            if (h != 0) {
                return h;
            }
            return Math.max(right(head.left), right(head.right));
        }

        // 为了验证
        // 对数器方法
        public static int getBSTSize(Node head) {
            if (head == null) {
                return 0;
            }
            ArrayList<Node> arr = new ArrayList<>();
            in(head, arr);
            for (int i = 1; i < arr.size(); i++) {
                if (arr.get(i).value <= arr.get(i - 1).value) {
                    return 0;
                }
            }
            return arr.size();
        }

        // 为了验证
        // 对数器方法
        public static void in(Node head, ArrayList<Node> arr) {
            if (head == null) {
                return;
            }
            in(head.left, arr);
            arr.add(head);
            in(head.right, arr);
        }

        // 为了验证
        // 对数器方法
        public static Node generateRandomBST(int maxLevel, int maxValue) {
            return generate(1, maxLevel, maxValue);
        }

        // 为了验证
        // 对数器方法
        public static Node generate(int level, int maxLevel, int maxValue) {
            if (level > maxLevel || Math.random() < 0.5) {
                return null;
            }
            Node head = new Node((int) (Math.random() * maxValue));
            head.left = generate(level + 1, maxLevel, maxValue);
            head.right = generate(level + 1, maxLevel, maxValue);
            return head;
        }
    }

}
